package cn.fansunion.leecode.todo;

import java.util.ArrayList;
import java.util.List;

import cn.fansunion.leecode.kit.TreeNode;

/**
 * 746. 使用最小花费爬楼梯 <br/>
 * 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。 <br/>
 * 一旦你支付此费用，即可选择向上爬一个或者两个台阶。 <br/>
 * 
 * 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。 <br/>
 * 
 * 请你计算并返回达到楼梯顶部的最低花费。 <br/>
 * 
 * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/min-cost-climbing-stairs 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 
 * @author wen.lei@brgroup.com
 *
 *         2022-3-9
 */
public class MinCostClimbingStairs {
    /* 示例 1：
    
    输入：cost = [10,15,20]
    输出：15
    解释：你将从下标为 1 的台阶开始。
    - 支付 15 ，向上爬两个台阶，到达楼梯顶部。
    总花费为 15 。
    示例 2：
    
    输入：cost = [1,100,1,1,1,100,1,1,100,1]
    输出：6
    解释：你将从下标为 0 的台阶开始。
    - 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
    - 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
    - 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
    - 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
    - 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
    - 支付 1 ，向上爬一个台阶，到达楼梯顶部。
    总花费为 6 。
     
    
    提示：
    
    2 <= cost.length <= 1000
    0 <= cost[i] <= 999
    */

    // 办法1：每2步，就选择最优的1步，但考虑到第3步时，之前的最优解，可能就不是最优解了;类似思路，不好搞
    // 办法2：穷举所有的路径，计算所有的成本，选出最低的
    public int minCostClimbingStairs2(int[] cost) {
        int n =0;
        int curCost=0;
        while(n<cost.length) {
            int curCost1= cost[0];
            int curCost2=cost[1];
            if(curCost1<=curCost2) {
                curCost+=curCost1;
                n++;
            }else {
                curCost+=curCost2;
                n+=2;
            }
        }
        return curCost;
    }
    
    public int minCostClimbingStairs(int[] cost) {
        List<Integer> totalCostList = new ArrayList<>();
        climbStairs(cost.length, 0, cost, totalCostList);
        return min(totalCostList);
    }

    private int min(List<Integer> totalCostList) {
        int min = Integer.MAX_VALUE;
        for (Integer totalCost : totalCostList) {
            if (totalCost < min) {
                min = totalCost;
            }
        }
        return min;
    }

    /**
     * 解题思路：穷举所有路径，找到所有的成本，选择最小的成本；遍历过程中：维护当前剩余的台阶，当前的成本，用递归来实现走1步和走2步的效果.<br/>
     * 受爬楼梯ClimbingStairs的影响，习惯性从后向前思考了，用的是(n-1)和(n-2)，而非(i+1)和(i+2)<br/>
     * 当剩余台阶为0和1时，说明爬楼梯的路径形成了，把完整路径的成本，维护到list<br/>
     * 为了方便确认代码思路和树的遍历过程，额外用treeNode维护递归的整个过程，方便人工回顾确认整个题的解决过程
     * 弊端：递归解法，cost数组太长时，内存溢出
     * @param stepRemaining
     * @param curCost
     * @param node
     * @param cost
     * @param totalCostList
     * @return
     */
    private int climbStairs(int stepRemaining, int curCost, int[] cost, List<Integer> totalCostList) {
        if (stepRemaining <= 0) {
            // System.out.println("curCost:" + curCost + "," + 0);
            totalCostList.add(curCost);
            return 0;
        } else if (stepRemaining == 1) {
            // System.out.println("curCost:" + curCost + "," + 1);
            totalCostList.add(curCost);
            return 1;
        } else {
            return climbStairs(stepRemaining - 1, curCost + cost[stepRemaining - 1], cost, totalCostList)
                + climbStairs(stepRemaining - 2, curCost + cost[stepRemaining - 2], cost, totalCostList);
        }
    }

    /**
     * 爬楼梯，自己研究探索解题思路
     * @param cost
     * @return
     */
    public List<Integer> climbStairsTree(int[] cost) {
        List<Integer> totalCostList = new ArrayList<>();
        TreeNode node = new TreeNode();
        climbStairsTree(cost.length, 0, node, cost, totalCostList);
        return totalCostList;
    }

    private int climbStairsTree(int stepRemaining, int curCost, TreeNode node, int[] cost,
        List<Integer> totalCostList) {
        node.val = stepRemaining;
        if (stepRemaining <= 0) {
            // System.out.println("curCost:" + curCost + "," + 0);
            totalCostList.add(curCost);
            return 0;
        } else if (stepRemaining == 1) {
            // System.out.println("curCost:" + curCost + "," + 1);
            totalCostList.add(curCost);
            return 1;
        } else {
            TreeNode left = new TreeNode();
            left.val = stepRemaining - 1;
            node.left = left;
            // left.prev=node;
            TreeNode right = new TreeNode();
            right.val = stepRemaining - 2;
            node.right = right;
            // right.prev=node;
            return climbStairsTree(stepRemaining - 1, curCost + cost[stepRemaining - 1], left, cost, totalCostList)
                + climbStairsTree(stepRemaining - 2, curCost + cost[stepRemaining - 2], right, cost, totalCostList);
        }
    }
}
